public class InsertionSort {
    public static void imp1(Integer[] array) {
        int length = array.length;

        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {
                swap(array, j, j - 1);
            }
        }
    }

    public static void imp2(Integer[] array) {
        int length = array.length;

        for (int i = 1; i < length; i++) {
            Integer element = array[i];
            int j = i;
            for (; j > 0 && array[j - 1] > element; j--) {
                array[j] = array[j - 1];
            }
            array[j] = element;
        }
    }

    public static void imp3(Integer[] array) {
        int length = array.length;

        for (int i = 1; i < length; i++) {
            Integer element = array[i];

            int low = 0;
            int high = i;
            while (low < high) {
                int mid = low + ((high - low) >> 1);

                if (element >= array[mid]) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }

            if (i - low >= 0) {
                System.arraycopy(array, low, array, low + 1, i - low);
            }

            array[low] = element;
        }
    }

    private static void swap(Integer[] array, int i, int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
